package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/">链表最大孪生和(Maximum Twin Sum of a Linked List)</a>
 * <p>
 * 在一个大小为n且n为 <b>偶数</b> 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
 * 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
 * </p>
 * <p><b>孪生和</b>定义为一个节点和它孪生节点两者值之和。</p>
 * <p>给你一个长度为偶数的链表的头节点 head ，请你返回链表的最大孪生和。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [5,4,2,1]
 *      输出：6
 *      解释：
 *          节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
 *          链表中没有其他孪生节点。
 *          所以，链表的最大孪生和是 6 。
 *
 * 示例 2：
 *      输入：head = [4,2,2,3]
 *      输出：7
 *      解释：
 *          链表中的孪生节点为：
 *          - 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
 *          - 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
 *          所以，最大孪生和为 max(7, 4) = 7 。
 *
 * 示例 3：
 *      输入：head = [1,100000]
 *      输出：100001
 *      解释：
 *          链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>链表的节点数目是 [2, 10^5] 中的 偶数 。</li>
 *      <li>1 <= Node.val <= 10^5</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/9 9:49
 */
public class LC2130MaximumTwinSumOfLinkedList_M {

    static class Solution {
        public int pairSum(ListNode head) {
            // 1.使用快慢指针找到链表的中点(mid=len/2-1)。
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            // 此时slow位于第一段链表的尾部，slow.next 为第二段链表的头部，用 fast 接收
            fast = slow.next;
            // 2.断开链表，并将第二段链表进行反转
            slow.next = null;
            fast = reserve(fast);
            // 3.汇总求值
            int maxSum = 0;
            while (head != null) {
                maxSum = Math.max(maxSum, head.val + fast.val);
                head = head.next;
                fast = fast.next;
            }
            return maxSum;
        }

        private ListNode reserve(ListNode head) {
            ListNode prevNode = null;
            ListNode currNode = head;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(5);
        head1.next = new ListNode(4);
        head1.next.next = new ListNode(2);
        head1.next.next.next = new ListNode(1);

        ListNode head2 = new ListNode(4);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(2);
        head2.next.next.next = new ListNode(3);

        Solution solution = new Solution();
        System.out.println(solution.pairSum(head1));
        System.out.println(solution.pairSum(head2));
    }
}
